1. Field of the Invention
The present invention relates in general to a system for laying out an integrated circuit (IC) and in particular to an IC layout system employing a database describing the IC as a modular hierarchy of cells.
2. Description of Related Art
FIG. 1 is a data flow diagram illustrating various steps of a typical IC design process. An IC designer usually begins the IC design process by producing a register transfer language (RTL) netlist 10 describing the IC circuit as a set of circuits nodes (“nets”) linked to terminals of logic devices described only in terms of the Boolean logic relating their input and output terminals. The designer then employs a circuit simulator and other tools 11 to verify the behavior of the circuit described by the netlist in response to a set of input signals. Since the RTL netlist models only circuit logic, simulation and verification at this point does not take into account signal path timing considerations. Having verified the logic of the circuit, the designer next uses a syntheses tool 12 to create a “gate level” netlist 14 modeling the circuit as a set of interconnected circuit components (cells), wherein each cell is described by an entry in a cell library 13. IC components described as library cells may range from individual transistors and small components such as logic gates incorporating several transistors up to very large components such as computer processors and memories. Each cell library entry includes a mathematical model of the cell describing its time-dependent behavior.
The gate level netlist 14 and the cell models included in the cell library enable circuit simulation and verification tools 11 to verify not only the circuit's logic but also its time-dependent behavior. However since the gate level netlist does not accurately model signal routing paths between the cells, simulation and verification tools 11 do not accurately account for those signal path delays.
An IC designer usually finds it convenient to create netlists 10 and 14 that are hierarchical in nature, grouping various cells into modules which may themselves be grouped into progressively higher level modules. For example a computer processor module may include many submodules such as registers, instruction decoders, cache memories and the like, which in turn may be formed by lower level modules or individual cells. RTL and gate level netlists for large IC designs can have many hierarchical levels.
FIG. 2 graphically illustrates a simple IC design including a top level module A formed by three lower level modules B-D. Module B in turn includes a set of low level “leaf” cells, E-H. Module C includes one submodule I and one cell J. Module D includes four cells K-N. Module I includes two cells O and P. While FIG. 2 depicts an IC formed by only 11 cells grouped into a three-level hierarchy of five modules, IC designs may include thousands or millions of cells grouped into a modular hierarchy having a great many levels; however the simple example of FIG. 2 is sufficient to illustrate a modular IC design.
Referring again to FIG. 1, a database compiler 18 processes gate level netlist 14 to produce a database 20 including a record corresponding to each cell of the IC. Each record references the cell library entry of its corresponding cell and indicates the circuit net to which the cell's terminals are to be connected. While a hierarchical IC design is easier for an engineer to comprehend than a “flat” design that does not organize cells into a hierarchy of modules, conventional placement and routing (P&R) tools that develop layouts of ICs described by netlists typically ignore the hierarchical nature of a design since the P&R tools normally place and route on a cell-by-cell basis. Hence when database compiler 18 processes a hierarchical gate level netlist 14 to produce a placement and routing database 20, database 20 includes only one record for each leaf cell to be included in the IC, and the database does not indicate the cells position in the modular hierarchy.
A typical database 20 will contain a separate record for each cell and a separate record for each terminal of each cell. Each cell record normally includes following fields:                Cell Name (Index field)        Library Reference        Location        First Terminal        
The Cell Name field is a unique identifier for that cell and is used as a database index. The Library Reference field points to the cell library for that cell. The Location field indicates the position and orientation of the cell in the substrate. The Location field is left empty when the P&R tool is be free to place the cell anywhere it wants to. However in some cases a designer may want to force the P&R tool to place a cell (usually a big cell such as an embedded memory) in some particular area of a substrate. In such case the designer provides data base compiler 18 with placement constraint data indicating the desired position and orientation of the cell, and the compiler puts the appropriate position and orientation information into the Location field of the database entry for that cell.
Each cell will have one or more input/output terminals and each terminal of a cell will have its own record in database 20. The entries for all terminals of a cell form a linked list, and the data base entry for the cell includes a field (First
Terminal) referencing the first entry of the linked list of entries for the cell's terminals.
The record for each terminal of a cell includes the following fields:                Terminal Name (Index field)        Cell Name        Library Terminal Reference        Net        Next Terminal        
The Terminal Name field is a unique name for the terminal and serves as the database index field. The Cell Name field points back to the database entry of the cell in which the terminal resides. The Library Terminal Reference field references the corresponding terminal of the prototype library cell. The Net field references an IC net (node) to which the terminal is to be connected. The Next Terminal field points to the terminal record for a next terminal (if any) of the cells. The Next Terminal field thereby links all of the terminal records for the cell into a linked list. Thus after positioning a cell in the layout, a P&R tool can traverse the linked list of the cell's terminal entries to determine the circuit net to which each terminal is to be connected.
Referring again to FIG. 1, based on the information contained in database 20 and in cell library 13, an automated placement and routing (P&R) tool 22 generates an IC layout 24 attempting to satisfy various timing and spatial constraints the designer has imposed on the layout. As it generates layout 24, P&R tool 22 determines where each cell described in database 20 is to be placed in the substrate and designs the signal routing paths interconnecting them. After P&R tool 22 has generated a preliminary layout of the IC described by database 20, a clock tree synthesis (CTS) tool 23 designs one, or more clock trees (networks of buffered signal paths) for routing clock signals supplied as input to the IC to each clocked IC device such as a register or a flip-flop. P&R tool 22 adjusts the IC layout 24 to accommodate the buffered signal paths forming the clock tree(s) synthesized by CTS tool 23.
After P&R tool 22 has created an IC layout 24, a netlist compiler 26 converts the layout back into a “layout level” netlist 28 that accurately models the time-dependent behavior not only of the cells forming the IC described by gate level netlist 14, but also the routing structures that interconnect those cells and the buffers and signal paths forming the IC's clock tree. The designer may then again use circuit simulation and verification tools 11 to analyze the layout level netlist 18 to accurately verify that the IC described by layout level netlist 28 will behave correctly. The designer may iteratively repeat the IC placement and routing process as necessary to find a placement and routing solution satisfying all timing and other constraints.
Min-cut Placement and Routing
A typical P&R tool iteratively searches for an appropriate cell layout satisfying the IC's various spatial, timing and other constraints. Various placement algorithms such as the widely used “min-cut” algorithm, can reduce the time a P&R tool needs to find an acceptable cell placement. A min-cut algorithm progressively divides the substrate area into smaller and smaller partitions. After dividing each partition into sub-partitions, it allocates the cells to its sub-partitions in a manner that attempts to minimize the number of signal paths that must pass between sub-partitions to interconnect the cells. Keeping signal paths between cells short improves the chances that the P&R tool will be able to find space for routing paths between the cells and improves the chances that the IC layout will satisfy various timing constraints. A min-cut placement algorithm therefore tries to minimize signal path lengths by positioning highly interconnected cells near one another.
FIG. 3 illustrate the min-cut process. Although ICs typically have thousands or millions of cells, for simplicity the example of FIG. 3 assumes the IC design includes only 26 cells A-Z that are to be placed within a substrate area 14. The min-cut algorithm initially divides the substrate into two partitions 16 and 18 and to randomly assign cells A-Z to the two partitions, thereby creating an initial “seed partitioning” 20. The placement algorithm then tries to optimize the manner in which cells are allocated to the two partitions 16 and 18 by moving cells from partition-to-partition trying to find a placement that minimizes the number of cell-to-cell connections that cross between the two partitions. For large ICs it would take too long to try all possible placements, so in many systems each cell is moved only once from one partition to another, and then moved back if the move increases the number of signal paths between the partitions.
After attempting to optimize the placement of cells between the two initial partitions 16 and 18, the algorithm divides partition 16 into two smaller partitions 21 and 22 and divides partition 18 into two smaller partitions 23 and 24. The algorithm then again tries to minimize the number of signal paths crossing between partitions 21 and 22 by appropriately allocating cells of partition 16 among partitions 21 and 22. The system will also try to minimize the number of signal paths between partitions 23 and 24 by allocating cells of partition 18 between those two partitions. After optimizing the cell placement within partitions 21-24, the system further divides each partition 21-24 to produce a set of eight partitions 31-38 and repeats the optimization process. The partitioning process continues until the partition size reaches a lower limit.
FIG. 4 is a flow chart illustrating a processes carried out by a typical P&R tool making use of a min-cut algorithm for generating a cell placement in an IC substrate. Steps 40-43 of FIG. 3 depict the min-cut process illustrated in FIG. 4. The P&R tool establishes a seed partition at step 40, optimizes the partition at step 41, and then (step 42) determines whether the number of cells per partition has fallen below the predetermined lower limit. If not, the system partitions the substrate again (step 43) and repeats the optimization step 41. The tool iteratively repeats steps 41-43 until partitions reach their lower size limit at step 42.
After using the min-cut algorithm to place the cells, the P&R tool tries to lay out signal paths for interconnecting the cells (step 44). If the P&R tool is able to successfully lay out all necessary signal paths (step 45) based on the layout developed at steps 40-43, then the layout is analyzed (step 46) to determine whether it meets all timing and other constraints. When all constraints are satisfied (step 47), then at step 48 the clock tree synthesis tool designs a clock tree for the layout, the placement and routing-tool incorporates the clock tree into the layout (step 49), and the placement and routing process ends.
However if step 45 determines a successful routing plan could not be developed or step 47 determines the IC layout does not satisfy all timing and other constraints, then the process starts over again at step 40 by choosing another seed partition. Since the IC layout to be routed at step 44 is a direct result of the seed partition randomly selected at step 40, different seed partitions selected at step 40 are likely to result in a different IC placement and routing plans. Thus the P&R algorithm searches for an acceptable IC layout by randomly choosing a succession of seed partitions and testing whether each seed partition results in a placement that can be successfully routed and which meets various circuit timing and other constraints. While the min-cut algorithm randomly chooses seed partitions, the iterative partitioning and optimization process increases the likelihood that the randomly chosen seed partition will result in an acceptable layout. The min-cut approach will typically find a suitable layout more quickly than a system that randomly chooses placement plans to be routed. However the process can still be time-consuming, particularly when the IC includes a large number of cells.
Clustering
As ICs become progressively larger, P&R tools have needed more time to lay out ICs despite the increasing speed of computers implementing the P&R tools. “Clusteringt” helps to reduce processing time needed to lay out an IC. Since the amount of time a min-cut layout system requires to carry out the optimization process after each division increases with the number of cells in the design, redefining a group of highly interconnected cells as a single “cluster cell” reduces the number of cells to be placed during each iteration of the optimization process. The paper entitled “Multilevel Circuit Partitioning” by Alpert et. al. published in 1997 by the Design Automation Conference describes a clustering process in which small cells are organized into large clusters during early stages of a min-cut layout process when partitions are large to reduce the number of cells that have to be moved from partition-to-partition when optimizing cell placement. The number of cells per cluster is progressively reduced as the partitions become smaller.
Partitioning
Another way a designer can reduce the time required to lay out an IC is to divide the circuit design into two or more partitions and to separately lay out each partition. (Note that in this context the word “partition” applies to a portion of the IC design, whereas in the context of the above-described min-cut placement process, the word “partition” applies to a portion of the substrate area in which cells of an IC are placed.) Since the time a min-cut placement algorithm needs to lay out an IC increases geometrically with the number of cells forming the IC, it can be much faster for a P&R tool to successively lay out M partitions of an IC having an average of N cells each than to lay out an entire IC having M*N cells. Further speed improvements can be had by using separate P&R tools to concurrently lay out the partitions. It can be helpful to partition a hierarchical design along modular lines since cells belonging to the same module tend to be highly interconnected with one another. Also, when modules of an IC design are placed in identifiable areas of a semiconductor substrate it is possible to later modify the layout of one module of an IC without having to extensively redo the layout,for the entire IC.
When partitioning an IC design, a designer typically creates a floor plan of the semiconductor substrate in which the IC is to be formed. The floor plan reserves an area of the substrate for each partition to hold the cells to be placed within each partition and positions and orients the partitions within the substrate. The designer also creates a “pin assignment” plan indicating where signal paths that interconnect the partitions are to cross the boundaries between the partitions. The floor and pin assignment plans act as constraints on the placement and routing of each partition. However the designer may have difficulty producing appropriate floor and pin assignment plans because it is often hard for a designer to accurately estimate an appropriate size, shape and position of the substrate area allocated to each partition and hard for the designer to determine where signal paths ought to cross partition lines.
In addition to creating floor and pin assignment plans, the designer must also determine how to partition the IC's timing constraints. A timing constraint typically specifies that a signal path formed by a set of cells connected between two circuit nodes A and B may have a signal path delay no greater than some maximum limit. A P&R tool tries to lay out the IC so that it satisfies all such timing constraints. However when the designer partitions the design in such a way that node A appears in one partition and node B appears in another partition, then the designer must also divide the timing constraint among the partitions by allocating a separate portion of the maximum allowable signal path delay to the portion of the signal path residing in each partition. It can be difficult and time consuming for the designer to determine how much of that maximum signal path delay to allocate to each partition.
What is needed is a placement and routing system that automatically partitions an IC and then separately generates the if layout for each partition. Accordingly such a P&R system must be able to automatically create appropriate floor and pin assignment plans based on the description of the IC included in the P&R database it receives as input.